Corelab Seminar
2019-2020
Alexander Meduna
Jumping Finite Automata
Abstract.
This talk proposes a new investigation area in automata theory — jumping finite automata. These automata work like classical finite automata except that they read input words discontinuously — that is, after reading a symbol, they can jump over some symbols within the words and continue their computation from there. The talk gives several results concerning jumping finite automata in terms of commonly investigated areas of automata theory, such as closure properties. Most importantly, it achieves several results that demonstrate differences between jumping finite automata and classical finite automata. In its conclusion, the talk formulates several open problems and suggests future investigation areas.
Short Bio: Prof. Alexander Meduna (born 1957 in Olomouc, Czech Republic) is a theoretical computer scientist and expert on compiler design, formal languages and automata. He is a professor of Computer Science at the Brno University of Technology. Formerly, he taught theoretical computer science at various European and American universities, including the University of Missouri, where he spent a decade teaching advanced topics of formal language theory. He wrote over ninety papers related to theoretical computer scientist. He is the author of several books, including:
Meduna, Alexander (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. ISBN 9781852330743.
Meduna, Alexander (2007). Elements of Compiler Design. CRC Press. ISBN 9781420063233.
Meduna, Alexander (2014). Formal Languages and Computation: Models and Their Applications. CRC Press. ISBN 9781466513457.
Meduna, Alexander; Švec, Martin (2005). Grammars with Context Conditions and Their Applications. John Wiley & Sons. ISBN 9780471736554.
Meduna, Alexander; Techet, Jiří (2010). Scattered Context Grammars and Their Applications. WIT Press. ISBN 9781845644260.
Meduna, Alexander; Zemek, Petr (2014). Regulated Grammars and Automata. Springer. ISBN 9781493903696.
Meduna, Alexander; Soukup, Ondřej (2017). Modern Language Models and Computation: Theory with Applications. Springer. ISBN 9783319630991.